//332 https://leetcode-cn.com/problems/reconstruct-itinerary/comments/

class Solution {
public:
    bool backstraing(int tickernum,vector<string>& result)
    {
        if(result.size() == tickernum+1)
            return true;
        //targets[result[result.size() - 1]];这里拿到的是result最后一个元素
        //targets是个string映射 map的内容，所以是这个值映射的内容，即机场到达位置和飞机次数
        for(pair<const string,int>& tar : targets[result[result.size() - 1]])
        {
            if(tar.second > 0)
            {
                result.push_back(tar.first);
                tar.second--;
                if(backstraing(tickernum,result)) return true;
                result.pop_back();
                tar.second++;
            }
        }
        return false;
    }
    unordered_map<string,map<string,int>> targets;
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        vector<string> result;
        //首先来说明一下这个是什么 类似于python中的for 结果 in 结构 中
        for(const vector<string> & vec : tickets)
        {
            targets[vec[0]][vec[1]]++; //这个++是让里面的值+1
        }
        result.push_back("JFK");
        backstraing(tickets.size(),result);
        return result;
    }
};
